/**Universidad del Valle de Guatemala 
 * Algoritmos y Estructura de Datos
 * Dennisse Escobar Delgado
 * Fecha: 20/09/2012
 * Produce la tabla de frecuencia de arboles binarios.  
 */


import java.util.LinkedList;
/**
 * Clase que representa un arbol huffman
 */

public class ArbolHuffman 
{
        //---------------------------------------------
        //ATRIBUTOS 
        //---------------------------------------------
        
        /**
         * Lista para almacenar el mensaje.
         */
        public LinkedList<ArbolBinario<Cadena>> lista;
        
        /**
         * Caracteres validos para el mensaje.
         */
    public String abc;
    
    /**
         * Representa la frecuencia de los caracteres.
         */
    public int[] frecuencia;
    
    //----------------------
        //CONSTRUCTOR
        //----------------------
        
        /**
         * Método que construye un nuevo arbol huffman
         */
    public ArbolHuffman()
    {
        lista = new LinkedList();
        abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ";
        frecuencia = new int[abc.length()];
    }
    
    //----------------------
        //METODOS
        //----------------------
        
        /**
         * Método para analizar un mensaje.
         * @param cad Mensaje ingresado por el usuario.
         */
    public void analizar(String cadena)
    {
        cadena = cadena.toUpperCase();
        inicializarFrecuencia();
        for (int i = 0; i < cadena.length(); i++)
                frecuencia[abc.indexOf(cadena.charAt(i))]++;
        crearArbol();
        crearArbolHuffman();
        crearCodigos();    
    }

    /**
         * Método para iniciar la frecuencia de cada caracter en cero.
         */
    public void inicializarFrecuencia()
    {
        for (int i = 0; i < frecuencia.length; i++)
            frecuencia[i] = 0;
    }

    /**
         * Método para construir un arbol binario.
         */
    public void crearArbol()
    {
        for (int i = 0; i < frecuencia.length; i++)
        {
            if (frecuencia[i] > 0)
            {
                Cadena temp = new Cadena();
                temp.cambiarFrecuencia(frecuencia[i]);
                temp.cambiarCadena(abc.substring(i,i+1));
                ArbolBinario<Cadena> arb = new ArbolBinario();
                arb.cambiarValor(temp);
                insertarArbol(arb);
            }
        }
    }
    
    /**
         * Método para insertar hijos al arbol.
         * @param t Caracter a insertar en el arbol
         */
    public void insertarArbol(ArbolBinario<Cadena> t)
    {
        boolean encontrado = false;
        int contador = 0;
        if (lista.size() == 0)
                lista.add(0, t);
        else
            while(!encontrado)
            {
                if (contador == lista.size())
                {
                        lista.add(contador, t);
                    encontrado = true;
                }
                else
                    if (t.darValor().darFrecuencia() > lista.get(contador).darValor().darFrecuencia())
                        contador++;
                    else
                    {
                        lista.add(contador, t);
                        encontrado = true;
                    }
            }
    }

    /**
         * Método para construir un arbol huffman.
         */
    public void crearArbolHuffman()
    {
        String str;
        int freq;
        while(lista.size() > 1)
        {
            str = lista.get(0).darValor().darCadena() + lista.get(1).darValor().darCadena();
            freq = lista.get(0).darValor().darFrecuencia() + lista.get(1).darValor().darFrecuencia();
            ArbolBinario<Cadena> temp = new ArbolBinario();
            temp.cambiarValor(new Cadena(str,freq));
            temp.cambiarIzquierda(lista.removeFirst());
            temp.cambiarDerecha(lista.removeFirst());
            lista.addFirst(temp);
        }          
    }
    
    /**
         * Método para crear los codigos de los caracteres.
         */
    public void crearCodigos()
    {
        String der = "0", izq = "1", cod;
        Cadena cad = lista.getFirst().darValor();
        for (int i = 0; i < cad.darCadena().length(); i++)
        {
            ArbolBinario<Cadena> temp = lista.getFirst();
            cod = "";
            while(!((temp.darIzquierda() == null) && (temp.darDerecha() == null)))
            {
                if (temp.darIzquierda().darValor().darCadena().contains(cad.darCadena().substring(i, i+1)))
                {
                    temp = temp.darIzquierda();
                    cod = cod + izq;
                }
                else
                {
                    temp = temp.darDerecha();
                    cod = cod + der;
                }   
            }
            temp.darValor().cambiarCodigo(cod);
        }
    }

    /**
         * Método para obtener la informacion de los codigos y frecuencias del mensaje.
         * @return Informacion del analisis de la cadena
         */
    public String toString()
    {
        String s = "Caracter          Frequencia          Codigo";
        Cadena cad = lista.getFirst().darValor();
        String[] arreglo = new String[cad.darCadena().length()+1];
        arreglo[0] = s;
        for (int i = 0; i < cad.darCadena().length(); i++)
        {
            ArbolBinario<Cadena> temp = lista.getFirst();
            while(!((temp.darIzquierda() == null) && (temp.darDerecha() == null)))
            {
                if (temp.darIzquierda().darValor().darCadena().contains(cad.darCadena().substring(i, i+1)))
                    temp = temp.darIzquierda();
                else
                    temp = temp.darDerecha();
            }
            arreglo[i+1] = ("   " + temp.darValor().darCadena() + "                           " + temp.darValor().darFrecuencia() + "                       " + temp.darValor().darCodigo());
        }
        for (int i = 1; i < arreglo.length - 1; i++)
            for(int j = i; j < arreglo.length; j++)
            {
                if(arreglo[i].charAt(0) > arreglo[j].charAt(0))
                {
                    s = arreglo[i];
                    arreglo[i] = arreglo [j];
                    arreglo[j] = s;
                }
            }
        s = "";
        for (int i = 0; i < arreglo.length; i++)
            s = s + arreglo[i] + "\n";
        return(s);
    }
}